import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Test {
}
class Solution {
    private List<List<Integer>> ans = new ArrayList<>();
    private boolean[] res;
    private void dfs(int[] nums, List<Integer> ret){
        if(ret.size() == nums.length){
            ans.add(new ArrayList<>(ret));
            return;
        }
        for(int i=0; i<nums.length; i++){
            if(i>0 && nums[i-1] == nums[i] && !res[i-1]) continue;
            if(!res[i]){
                res[i] = true;
                ret.add(nums[i]);
                dfs(nums,ret);
                ret.remove(ret.size()-1);
                res[i] = false;
            }
        }
    }
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<Integer> ret = new ArrayList<>();
        res = new boolean[nums.length];
        Arrays.sort(nums);
        dfs(nums,ret);
        return ans;

    }
}
class Solution1 {
    private List<List<Integer>> ans = new ArrayList<>();
    private boolean[] res;
    private void dfs(int[] nums, List<Integer> ret){
        if(ret.size() == nums.length){
            ans.add(new ArrayList<>(ret));
            return;
        }
        for(int i=0; i<nums.length; i++){
            if(!res[i]){
                res[i] = true;
                ret.add(nums[i]);
                dfs(nums,ret);
                ret.remove(ret.size()-1);
                res[i] = false;
            }
        }
    }
    public List<List<Integer>> permute(int[] nums) {
        List<Integer> ret = new ArrayList<>();
        res = new boolean[nums.length];
        dfs(nums,ret);
        return ans;
    }

}
class Solution2 {
    List<List<String>> ans = new ArrayList<>();
    List<String> ret = new ArrayList<>();
    private void dfs(char[][] chessboard, int n, int row){
        if(row == n){
            ans.add(new ArrayList<>(ret));
            return;
        }
        for(int i=0; i<n; i++){
            if(isValid(chessboard,row,i,n)){
                chessboard[row][i] = 'Q';
                ret.add(String.copyValueOf(chessboard[row]));
                dfs(chessboard,n,row+1);
                ret.remove(ret.size()-1);
                chessboard[row][i] = '.';
            }
        }
    }
    private boolean isValid(char[][] chessboard, int i, int j, int n){
        for(int k=0; k<n; k++){
            if(k!=i && chessboard[k][j] == 'Q')
                return false;
            if(k!=j && chessboard[i][k] == 'Q')
                return false;
        }
        for(int x=0; x<n; x++){
            for(int y=0; y<n; y++){
                if(x!=i && y!=j && x+y == i+j && chessboard[x][y] == 'Q')
                    return false;
                if(x!=i && y!=j && x-y == i-j && chessboard[x][y] == 'Q')
                    return false;
            }
        }
        return true;
    }
    public List<List<String>> solveNQueens(int n) {
        char[][] chessboard = new char[n][n];//棋盘
        for(int i=0; i<n; i++){
            Arrays.fill(chessboard[i],'.');
        }
        dfs(chessboard,n,0);
        return ans;
    }
}
class Solution3 {
    private boolean dfs(char[][] board){
        for(int i=0; i<board.length; i++){//[i][j]代表9x9的方格位置
            for(int j=0; j<board[0].length; j++){
                if(board[i][j] == '.'){
                    for(char k='1'; k<='9'; k++){//遍历取值
                        if(isValid(board,k,i,j)){
                            board[i][j] = k;
                            boolean res = dfs(board);
                            if(res==true) return true;
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    private boolean isValid(char[][] board, char k, int i, int j){
        for(int x=0; x<board.length; x++){//判断行/列是否有相同的数字
            if(board[i][x]==k){
                return false;
            }
            if(board[x][j]==k){
                return false;
            }
        }
        int startRow = (i / 3) * 3;
        int startCol = (j / 3) * 3;
        for (int x=startRow; x<startRow+3; x++) { // 判断9方格里是否重复
            for (int y=startCol; y<startCol+3; y++) {
                if (board[x][y]==k ) {
                    return false;
                }
            }
        }
        return true;
    }
    public void solveSudoku(char[][] board) {
        dfs(board);
    }
}